﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GKS.DataTypes.Trees {
    /// <summary>
    /// A Binary Search Tree (BST) implementation
    /// </summary>
    /// <typeparam name="E"></typeparam>
    public class BinarySearchTree<K, V> /*: ICollection<TreeNode<K,V>>*/ where K:IComparable<K>, new() {
        #region instance variables

        #endregion

        #region properties

        #endregion

        #region constructors

        #endregion

        #region public methods

        #endregion

        #region private methods

        #endregion

        //private BSTNode<E> root;

        //#region properties
        ////public int Level { get; private set; }
        //public int Depth { get { return root.Depth; } }
        //#endregion

        //#region constructors
        //public BinarySearchTree(E element){
        //    root = new BSTNode<E>(element, null, null, null, 0, 0);
        //}
        //#endregion

        //#region methods
        //public int Level(E element) {
        //    List<BSTNode<E>> path;
            
        //    return root.Search(element, out path) ? -1 : path.Count - 1;
        //}

        //public bool Add(E element) {
        //    //throw new NotImplementedException();
        //    return root.Add(element);
        //}

        //public bool Add(E element, out E[] path) {
        //    List<BSTNode<E>> pathList = new List<BSTNode<E>>();
        //    bool result = root.Add(element, out pathList);
        //    path = new E[pathList.Count];

        //    if (result) {
        //        for (int i = 0; i < pathList.Count; i++) {
        //            path[i] = pathList.ElementAt(i).Element;
        //        }
        //    } else {
        //        path = new E[0];
        //    }

        //    return result;
        //}

        //public bool Remove(E element, out E removedElement) {
        //    throw new NotImplementedException();
        //}

        //public bool Remove(E element) {
        //    //throw new NotImplementedException();
        //    BSTNode<E> toRemove = root.Search(element);

        //    if (toRemove == null) {
        //        return false;
        //    }

        //    if (root.Element.Equals(element) && root.LeftChild == null && root.RightChild == null) {
        //        root = null;
        //        return true;
        //    }

        //    return toRemove.Remove();
        //}

        //public bool Search(E element, out E[] path) {
        //    List<BSTNode<E>> pathList;
        //    bool result = root.Search(element, out pathList);
        //    path = new E[pathList.Count];

        //    if (result) {
        //        for (int i = 0; i < pathList.Count; i++) {
        //            path[i] = pathList.ElementAt(i).Element;
        //        }
        //    } else {
        //        path = new E[0];
        //    }

        //    return result;
        //}

        //public void Print() {
        //    root.Print("");
        //}
        //#endregion

        ///// <summary>
        ///// The class that implements the node for the BST.
        ///// </summary>
        ///// <typeparam name="E">The element of the node.</typeparam>
        //private class BSTNode<T> where T : IComparable<T>, new() {
        //    #region parameters
        //    /// <summary>
        //    /// The level of the current node in the tree it belongs in.
        //    /// </summary>
        //    public int Level { get; set; } 
            
        //    /// <summary>
        //    /// The depth of the subtree from this node and downwards.
        //    /// </summary>
        //    public int Depth { get; set; }
            
        //    /// <summary>
        //    /// The element of the node.
        //    /// </summary>
        //    public T Element { get; set; }
            
        //    /// <summary>
        //    /// The parent of this node.
        //    /// </summary>
        //    public BSTNode<T> Parent { get; set; }
            
        //    /// <summary>
        //    /// The left child of this node.
        //    /// </summary>
        //    public BSTNode<T> LeftChild { get; set; }
            
        //    /// <summary>
        //    /// The right child of this node.
        //    /// </summary>
        //    public BSTNode<T> RightChild { get; set; }
        //    #endregion 

        //    #region constructors
        //    /// <summary>
        //    /// A constructor of a node.
        //    /// </summary>
        //    /// <param name="element">The element of this node.</param>
        //    /// <param name="parent">The parent of this node.</param>
        //    /// <param name="left">The left child of this node.</param>
        //    /// <param name="right">The right child of this node.</param>
        //    /// <param name="level">The level of this node in the tree it belongs to.</param>
        //    /// <param name="depth">The depth of the subtree from this node and downwards.</param>
        //    public BSTNode(T element, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right, int level, int depth) {
        //        Element = element;
        //        Parent = parent;
        //        LeftChild = left;
        //        RightChild = right;
        //        Level = level;
        //        Depth = depth;
        //    }

        //    public BSTNode(T element, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) 
        //        : this(element, parent, left, right, parent.Level + 1, Math.Max(left.Depth, right.Depth)) { }

        //    public BSTNode(T element, BSTNode<T> parent) : this(element, parent, null, null, parent.Level + 1, 0) { }

        //    public BSTNode(T element) : this(element, null, null, null, 0, 0) { }
        //    #endregion

        //    #region methods
        //    /// <summary>
        //    /// A method that adds the wanted element in the subtree of this node.
        //    /// </summary>
        //    /// <param name="element">The element to add to the subtree.</param>
        //    /// <returns>TRUE if the element was added, FALSE otherwise.</returns>
        //    /// <remarks>If another element equals to the specified one already exists in the tree, no addition is done.</remarks>
        //    public bool Add(T element) {
        //        int comparison = element.CompareTo(this.Element);
        //        int leftDepth, rightDepth;

        //        if (comparison < 0) {           // we have to go left
        //            if (LeftChild == null) {            // the element can be added
        //                LeftChild = new BSTNode<T>(element, this); 
        //            } else {                            // the element can not be added
        //                LeftChild.Add(element);             
        //            }
        //        } else if (comparison > 0) {    // we have to go right
        //            if (RightChild == null) {
        //                RightChild = new BSTNode<T>(element, this);
        //            } else {
        //                RightChild.Add(element);
        //            }
        //        } else {
        //            return false;
        //        }

        //        leftDepth = LeftChild == null ? 0 : LeftChild.Depth;
        //        rightDepth = RightChild == null ? 0 : RightChild.Depth;
        //        Depth = Math.Max(leftDepth, rightDepth) + 1;

        //        return true;
        //    }

        //    public bool Add(T element, out List<BSTNode<T>> path) {
        //        int comparison;// = element.CompareTo(this.Element);
        //        path = new List<BSTNode<T>>();
        //        BSTNode<T> node = this;
        //        bool result = false;
        //        BSTNode<T>[] pathArray;
        //        int leftDepth, rightDepth;

        //        do {
        //            comparison = element.CompareTo(node.Element);
        //            path.Add(node);

        //            if (comparison < 0) {           // go left
        //                if (node.LeftChild == null) {
        //                    node.LeftChild = new BSTNode<T>(element, node);
        //                    result = true;
        //                } else {
        //                    node = node.LeftChild;
        //                }
        //            } else if (comparison > 0) {    // go right
        //                if (node.RightChild == null) {
        //                    node.RightChild = new BSTNode<T>(element, node);
        //                    result = true;
        //                } else {
        //                    node = node.RightChild;
        //                }
        //            } else {
        //                break;
        //            }
        //        } while (!result);

        //        if (result) {       // the element was added to the tree
        //            // update the depth of the various subtrees
        //            pathArray = path.ToArray();

        //            for (int i = pathArray.Length - 1; i >= 0; i--) {
        //                leftDepth = pathArray[i].LeftChild == null ? 0 : pathArray[i].LeftChild.Depth;
        //                rightDepth = pathArray[i].RightChild == null ? 0 : pathArray[i].RightChild.Depth;
        //                pathArray[i].Depth = Math.Max(leftDepth, rightDepth) + 1;
        //            }
        //        }

        //        return result;
        //    }

        //    /// <summary>
        //    /// A method that searches for the wanted element in the subtree of this node.
        //    /// </summary>
        //    /// <param name="element">The element to search for.</param>
        //    /// <returns>The node containing the element.</returns>
        //    public BSTNode<T> Search(T element) {
        //        int comparison;
        //        BSTNode<T> node = this;

        //        do {
        //            comparison = element.CompareTo(node.Element);

        //            if (comparison < 0) {       // we have to go left
        //                if (node.LeftChild == null) { return null; }

        //                node = node.LeftChild;
        //            } else if (comparison > 0) {    // we have to go right
        //                if (node.RightChild == null) { return null; }

        //                node = node.RightChild;
        //            } else {            // we found the node we were looking for
        //                return node;
        //            }
        //        } while (true);
        //    }

        //    /// <summary>
        //    /// A method that searches for the wanted element in the subtree of this node.
        //    /// </summary>
        //    /// <param name="element">The element to search for.</param>
        //    /// <param name="path">The path that was followed while looking for the element.</param>
        //    /// <returns>TRUE if the element was found, FALSE otherwise.</returns>
        //    public bool Search(T element, out List<BSTNode<T>> path) {
        //        int comparison;
        //        BSTNode<T> node = this;
        //        path = new List<BSTNode<T>>();

        //        do {
        //            comparison = element.CompareTo(node.Element);

        //            if (comparison < 0) {       // go left
        //                if (node.LeftChild == null) { return false; }

        //                path.Add(node);
        //                node = node.LeftChild;
        //            } else if (comparison > 0) {    // go right
        //                if (node.RightChild == null) { return false; }

        //                path.Add(node);
        //                node = node.RightChild;
        //            } else {                // found it
        //                path.Add(node);
        //                return true;
        //            }
        //        } while (true);
        //    }

        //    public void Print(string prefix) {
        //        if (RightChild != null) {
        //            RightChild.Print(string.Format("{0}\t", prefix));
        //        }

        //        Console.WriteLine("{0}[{1},{2}]", prefix, Element, Depth);

        //        if (LeftChild != null) {
        //            LeftChild.Print(string.Format("{0}\t", prefix));
        //        }
        //    }

        //    /// <summary>
        //    /// A method that removes this node.
        //    /// </summary>
        //    /// <returns>TRUE if the node was removed, FALSE otherwise.</returns>
        //    public bool Remove() {
        //        bool ris = false;
        //        int leftDepth, rightDepth;
        //        BSTNode<T> next = this, node;
        //        List<BSTNode<T>> visitedNodes = new List<BSTNode<T>>();
        //        BSTNode<T>[] visitedNodesArray;

        //        visitedNodes.Add(next);

        //        do {
        //            node = next;    
        //            leftDepth = node.LeftChild == null ? 0 : node.LeftChild.Depth + 1;
        //            rightDepth = node.RightChild == null ? 0 : node.RightChild.Depth + 1;

        //            if (leftDepth > 0 || rightDepth > 0) {
        //                if (leftDepth >= rightDepth) {
        //                    next = node.LeftChild;
        //                    visitedNodes.Add(next);

        //                    while (next.RightChild != null) {
        //                        next = next.RightChild;
        //                        visitedNodes.Add(next);
        //                    }
        //                } else {
        //                    next = node.RightChild;
        //                    visitedNodes.Add(next);

        //                    while (next.LeftChild != null) {
        //                        next = next.LeftChild;
        //                        visitedNodes.Add(next);
        //                    }
        //                }

        //                //node.Element = next.Element;
        //            } 
                    
        //            if(next.LeftChild == null && next.RightChild == null) {
        //                if (next.Element.CompareTo(next.Parent.Element) < 0) {
        //                    node.Element = next.Element;
        //                    next.Parent.LeftChild = null;
        //                } else {
        //                    node.Element = next.Element;
        //                    next.Parent.RightChild = null;
        //                }

        //                next.Parent = null;
        //                ris = true;
        //                visitedNodes.RemoveAt(visitedNodes.Count - 1);
        //                break;
        //            }

        //            node.Element = next.Element;
        //        } while (true);

        //        visitedNodesArray = visitedNodes.ToArray();

        //        for (int i = visitedNodesArray.Length - 1; i >= 0; i--) {
        //            leftDepth = visitedNodesArray[i].LeftChild == null ? 0 : visitedNodesArray[i].LeftChild.Depth + 1;
        //            rightDepth = visitedNodesArray[i].RightChild == null ? 0 : visitedNodesArray[i].RightChild.Depth + 1;
        //            visitedNodesArray[i].Depth = Math.Max(leftDepth, rightDepth);
        //        }

        //        return ris;
        //    }
        //    #endregion
        //}
    }
}
